#include <string>
#include <unordered_map>
#include "gtest/gtest.h"

using namespace std;

string minWindow(string s, string t){
  std::unordered_map<char,int> need;
  std::unordered_map<char,int> window;

  //1.fill need with string t
  for (char c : t) {
    need[c]++;//record count of each number in sub string
  }

  int start = 0, left = 0, right = 0;
  int valid = 0;
  int len = UINT16_MAX;

  //2.increase right index until reach the whole string s
  while(right < s.size()){
    char c = s[right];
    right++;

    //2.1 need include c,to reduce useless operation
    if(need.count(c)){
      window[c]++;
      if(window[c] == need[c])
        valid++;
    }

    //2.2 judge left window need shrink
    while(valid == need.size()){
      //2.3 save the temp result
      if(right - left < len){
        start = left;
        len = right - left;
      }

      //2.4 after save result,we move the left side
      char d = s[left];
      left++;

      if(need.count(d)){
        if(window[d] == need[d])
          valid--;
        window[d]--;
      }
    }
  }
  return len == UINT16_MAX? "" : s.substr(start,len);
}

TEST(TestFindSubstr, TestFindSubstr){
  string targetStr = "EBBANCF";
  string subStr = "ABC";
  string result = minWindow(targetStr, subStr);
  cout<< "result:" <<result<<endl;
}